import java.util.Arrays;

public class quickSort {
    public static void main(String[] args) {
        int[] array = {113,24,29,12,78,9,2,67};
        quickSort1(array);
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort1(int[] array) {
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int start, int end) {
        if (start >= end){
            return;
        }
        int pivoit = Hare(array,start,end);
        quick(array,start,pivoit-1);
        quick(array,pivoit+1,end);
    }

    private static int Hare(int[] array, int left, int right) {
        int i = left;
        int pivoit = array[left];
        while (left < right){

            while (left < right && array[right] >= pivoit){
                right--;
            }
            while (left < right && array[left] <= pivoit){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }

    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}
